package 数据结构.树;

import java.util.*;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-01
 */
public class JZ77按之字形顺序打印二叉树 {
    //队列
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)
            return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot);
        int time = 1;
        while (!q.isEmpty()){
            int n = q.size();
            ArrayList<Integer> alist = new ArrayList<Integer>();
            for(int i=0;i<n;i++){
                TreeNode node = q.poll();
                if(node.left!=null)
                        q.offer(node.left);
                if(node.right!=null)
                        q.offer(node.right);
                alist.add(node.val);
            }
            if(time%2==0)
                Collections.reverse(alist);
            list.add(alist);
            time++;
        }
        return list;
    }

    //栈
    public ArrayList<ArrayList<Integer> > Print2(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        if(head == null)
            //如果是空，则直接返回空list
            return res;
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        //放入第一次
        s1.push(head);
        while(!s1.isEmpty() || !s2.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            //遍历奇数层
            while(!s1.isEmpty()){
                TreeNode node = s1.pop();
                //记录奇数层
                temp.add(node.val);
                //奇数层的子节点加入偶数层
                if(node.left != null)
                    s2.push(node.left);
                if(node.right != null)
                    s2.push(node.right);
            }
            //数组不为空才添加
            if(temp.size() != 0)
                res.add(new ArrayList<Integer>(temp));
            //清空本层数据
            temp.clear();
            //遍历偶数层
            while(!s2.isEmpty()){
                TreeNode node = s2.pop();
                //记录偶数层
                temp.add(node.val);
                //偶数层的子节点加入奇数层
                if(node.right != null)
                    s1.push(node.right);
                if(node.left != null)
                    s1.push(node.left);
            }
            //数组不为空才添加
            if(temp.size() != 0)
                res.add(new ArrayList<Integer>(temp));
            //清空本层数据
            temp.clear();
        }
        return res;
    }
}
